package cn.oliver.dbindexresearch.index;

import cn.oliver.dbindexresearch.util.HashUtil;
import cn.oliver.dbindexresearch.util.MathUtil;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;

import java.util.*;

/**
 * 线性哈希算法
 */
@SuppressWarnings({"DuplicatedCode", "Duplicates"})
public class LinearHash {

    private List<Bucket> buckets;
    private int allKeys;
    private final float FILL_FACTOR = 0.75f;//装填因子

    public LinearHash() {
        totalKeys = 0;
        buckets = new ArrayList<>();
        buckets.add(new Bucket());
        buckets.add(new Bucket());
    }

    /**
     * 插入元素
     * @param key       索引键
     * @param value     索引值
     */
    public void insert(String key, Object value){

        int n = buckets.size();//桶的数量
        int i = (int)Math.ceil(MathUtil.log2(n));//桶的数量换算成二进制需要的位数
        int m = hash(key, n);
        //获取下标为m的桶
        Bucket bucket = buckets.get(m);

        //循环，直到找到一个没有装满的桶
        Bucket finalBucket = findNotFullBucket(bucket);
        int emptyIndex = findFirstEmptyIndex(finalBucket);
        finalBucket.values[emptyIndex] = new Data(key, value);
        finalBucket.valuesCounter++;
        totalKeys++;

        //计算平均入住率，如果大于阈值则需要增加新桶
        double averageOccupancy = totalKeys*1f / (n * Bucket.BLOCK_SIZE);
        if (averageOccupancy > AVERAGE_OCCUPANCY_RATE_THRESHOLD){
            //添加新桶
            Bucket newBucket = new Bucket();
            buckets.add(newBucket);

            int realN = n - (int)Math.pow(2, i-1);
            int j = (int)Math.ceil(MathUtil.log2(n + 1));
            Bucket currentBucket = buckets.get(realN);
            while(true){
                for (int x=0; x<currentBucket.values.length; x++){
                    Data data = currentBucket.values[x];
                    if (data == null){
                        continue;
                    }
                    int dataKeyHash = HashUtil.time33(data.key);
                    int dataM = dataKeyHash % (int)Math.pow(2, j);
                    if (dataM == n){
                        finalBucket = findNotFullBucket(newBucket);
                        emptyIndex = findFirstEmptyIndex(finalBucket);
                        finalBucket.values[emptyIndex] = data.copy();
                        finalBucket.valuesCounter++;
                        currentBucket.values[x] = null;
                        currentBucket.valuesCounter--;
                    }
                }
                if(currentBucket.nextBucket == null){
                    break;
                }
                currentBucket = currentBucket.nextBucket;
            }
        }
    }

    /**
     * 根据第一个桶找到后续的第一个不满的桶
     * @param firstBucket
     * @return
     */
    private Bucket findNotFullBucket(Bucket firstBucket){
        Bucket tmpBucket = firstBucket;
        while (tmpBucket.valuesCounter == Bucket.BLOCK_SIZE){
            if (tmpBucket.nextBucket == null){
                tmpBucket.nextBucket = new Bucket();
                tmpBucket = tmpBucket.nextBucket;
                break;
            }
            tmpBucket = tmpBucket.nextBucket;
        }
        return tmpBucket;
    }

    /**
     * 找到某个块儿中第一个数据为null的位置的下标
     * @param bucket
     * @return
     */
    private int findFirstEmptyIndex(Bucket bucket){
        int index = 0;
        for (int i=0; i<bucket.values.length; i++){
            if (bucket.values[i] == null){
                index = i;
                break;
            }
        }
        return index;
    }

    /**
     * 打印索引结构
     * @return
     */
    public String structure(){
        JSONArray bucketArray = new JSONArray();
        for (int i=0; i<buckets.size(); i++){
            JSONArray currentArray = new JSONArray();
            int j = 0;
            Bucket currentBucket = buckets.get(i);
            while(true){
                JSONObject bucketInfo = new JSONObject();
                bucketInfo.put("name", String.format("bucket%d-%d", i, j++));
                bucketInfo.put("values", currentBucket.valuesCounter);
                currentArray.add(bucketInfo);
                if (currentBucket.nextBucket == null){
                    break;
                }
                currentBucket = currentBucket.nextBucket;
            }
            bucketArray.add(currentArray);
        }
        return bucketArray.toJSONString();
    }

    /**
     * 根据键值查找符合条件的记录
     * @param key 键值
     * @return
     */
    public List<Object> find(String key){
        List<Object> objectList = new ArrayList<>();
        Set<Integer> indexSet = new HashSet<>();
        for (int x=2; x<=buckets.size(); x++){
            int m = hash(key, x);
            if (indexSet.contains(m)){
                continue;
            }
            indexSet.add(m);

            //获取下标为m的桶
            Bucket bucket = buckets.get(m);

            //遍历该桶及其溢出桶，收集符合条件的数据
            while (true){
                for (int y=0; y<bucket.values.length; y++){
                    Data data = bucket.values[y];
                    if (data == null){
                        continue;
                    }
                    if (data.key.equals(key)){
                        objectList.add(data.value);
                    }
                }
                if (bucket.nextBucket == null){
                    break;
                }
                bucket = bucket.nextBucket;
            }
        }
        return objectList;
    }

    /**
     * 删除某个键值对应数据
     * @param key 键值
     */
    public void delete(String key){
        Set<Integer> indexSet = new HashSet<>();
        for (int x=2; x<=buckets.size(); x++){
            int m = hash(key, x);
            if (indexSet.contains(m)){
                continue;
            }
            indexSet.add(m);

            //获取下标为m的桶
            Bucket bucket = buckets.get(m);

            //遍历该桶及其溢出桶，收集符合条件的数据
            while (true){
                for (int y=0; y<bucket.values.length; y++){
                    Data data = bucket.values[y];
                    if (data == null){
                        continue;
                    }
                    if (data.key.equals(key)){
                        bucket.values[y] = null;
                        bucket.valuesCounter--;
                        totalKeys--;
                    }
                }
                if (bucket.nextBucket == null){
                    break;
                }
                bucket = bucket.nextBucket;
            }
        }
    }

    /**
     * 线性哈希函数
     * @param key 键值
     * @param n 哈希桶数量
     * @return
     */
    private int hash(String key, int n){
        int i = (int)Math.ceil(MathUtil.log2(n));//桶的数量换算成二进制需要的位数
        int k = HashUtil.time33(key);//key的hash值
        k = k >= 0? k: 0-k;
        int m = k % (int)Math.pow(2, i);//逻辑桶下标

        //如果计算真桶的下标
        int realM = m;
        if (m >= n){
            realM = m - (int)Math.pow(2, i - 1);
        }
        return realM;
    }

    /**
     * 数据桶
     */
    public static class Bucket{
        public static final int BLOCK_SIZE = 4096;
        public Data[] values = new Data[BLOCK_SIZE];
        public int valuesCounter;
        public Bucket nextBucket;
    }

    /**
     * 数据
     */
    public static class Data{
        public String key;
        public Object value;
        public Data(String key, Object value){
            this.key = key;
            this.value = value;
        }

        public Data copy(){
            return new Data(key, value);
        }
    }
}
